package com.shellSort;

import com.Sort;

/**
 * 算法（第四版）上的希尔排序示例
 *
 * @param <Item>
 */
public class ShellSortEnhance<Item extends Comparable<Item>> extends Sort<Item> {
    public void sort(Item[] comparableArray) {
        int length = comparableArray.length;
        int step = 1;
        while (step < length / 3) {
            step = 3 * step;
        }

//        逐渐的合并分组，通过将步进减小到1，来合并分组
        while (step >= 1) {

//          对每一个步进分组都进行插入排序
            //        以输入的步进，遍历该步进分组中未排序的元素，起始值为该步进分组的组号
            for (int unSortIndex = step; unSortIndex < length; unSortIndex++) {

//            以输入的步进，便利该分组中已排序的元素，起始值为该步进分组的组号
                for (int sortedIndex = unSortIndex; sortedIndex >= unSortIndex && super.less(comparableArray[sortedIndex], comparableArray[sortedIndex - step]); sortedIndex -= step) {

                    super.exchange(comparableArray, sortedIndex, sortedIndex - step);
                }
            }
            step /= 3;
        }
    }
}
